home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Just Call Me Internet
/
Just Call Me Internet.iso
/
prog
/
atari
/
m2
/
cat3src
/
cat
/
boyermoo.d
< prev
next >
Wrap
Text File
|
1997-10-26
|
4KB
|
64 lines
DEFINITION MODULE BoyerMoore;
(*==============================================================*
* Modul: Stringsuchen nach Boyer-Moore *
* Autor: Dirk Steins/Johannes Gttker-Schnetmann *
* erstellt am: 18.04.1992 *
* letzte nderung am: 19.04.1992 *
* Version: 1.0 *
* Interne Version: V#0001 *
*==============================================================*
Schnelle Stringsuche nach Boyer-Moore, vgl. N. Wirth: Algorithmen
und Datenstrukturen mit Modula-2, Teubner 1986, S. 67ff
bernommen aus GMEKernel von Johannes Leckebusch, Peter Hellinger
Mit einem herzlichen Dank an diese beiden!
*----------------------------------------------------------------------------
* Datum Vers. Autor nderung (Arbeitsbericht)
*----------------------------------------------------------------------------
*----------------------------------------------------------------------------
*)
TYPE longString = ARRAY[0..MAX(LONGINT)] OF CHAR;
TYPE longPtr = POINTER TO longString;
TYPE tableType = ARRAY[0C..377C] OF CARDINAL;
(* Tabelle der Zeichenpositionen im String (von hinten) *)
PROCEDURE InitTable(VAR table : tableType; (* Tabelle fr Boyer-Moore-Suche *)
VAR subStr : ARRAY OF CHAR; (* Zu suchender String *)
len : CARDINAL; (* Lnge dieses Strings *)
gross : BOOLEAN; (* gro-klein unterscheiden *)
reverse: BOOLEAN); (* Rckwrts suchen *)
(* len mu grer als 0 sein! *)
(* Wenn gross TRUE ist, wird der String entsprechend gewandelt *)
PROCEDURE Pos (start : LONGINT; (* Startposition im verwendeten Puffer *)
str : longPtr; (* Zeiger auf den Pufferbereich *)
pLen : LONGINT; (* Lnge dieses Bereiches *)
REF substr : ARRAY OF CHAR; (* gesuchter String *)
len : INTEGER; (* Lnge dieses Strings *)
gross : BOOLEAN; (* gross-klein unterscheiden? *)
REF table : tableType): LONGINT; (* Mit InitTable angelegte Tabelle *)
(* Da die zu verarbeitenden Speicherblcke auch recht gro werden knnen sollen :-) *)
(* hier die Deklaration als LONGINT. Man knnte die Suche notfalls auch stckeln, *)
(* dann knnte es aber Probleme geben, wenn der zu suchende String gerade auf der *)
(* Blockgrenze steht. Lsung dazu: Einfach um 32k - Stringlnge nur vorrcken, das *)
(* wre mir aber trotzdem im Moment etwas zuviel Aufwand. *)
(* Eigentlich ist die Benutzung von LONGINT auch Verschwendung von 2 GB, falls aber *)
(* jemand mehr als 2 GB im Rechner hat, dann kann er sich ja mal melden und bekommt *)
(* dann eine Sonderversion.. :-) *)
PROCEDURE BackPos (start : LONGINT; (* Startposition im verwendeten Puffer *)
str : longPtr; (* Zeiger auf den Pufferbereich *)
pLen : LONGINT; (* Lnge dieses Bereiches *)
REF substr : ARRAY OF CHAR; (* gesuchter String *)
len : INTEGER; (* Lnge dieses Strings *)
gross : BOOLEAN; (* gross-klein unterscheiden? *)
REF table : tableType): LONGINT; (* Mit InitTable angelegte Tabelle *)
(* Macht genau das gleiche wie Pos, sucht nur Rckwrts im Buffer *)
END BoyerMoore.